package com.duoduo.链表;

import com.duoduo.ListNode;

import java.util.List;

/**
 * @program: algorithm
 * @description: 反转链表II92
 * 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
 *  
 * 输入：head = [1,2,3,4,5], left = 2, right = 4
 * 输出：[1,4,3,2,5]
 * 示例 2：
 * <p>
 * 输入：head = [5], left = 1, right = 1
 * 输出：[5]
 * @author: chaidl  ！
 * @create: 2022-05-17 22:11
 */
public class 反转链表II92 {
	public ListNode reverseBetween1(ListNode head, int left, int right) {
		// 设置 dummyNode 是这一类问题的一般做法
		ListNode dummyNode = new ListNode(-1);
		dummyNode.next = head;
		ListNode pre = dummyNode;
		//	将preNode移动left-1步，那么他就在第一个需要反转的元素之前
		for (int i = 0; i < left - 1; i++) {
			pre = pre.next;
		}
		ListNode cur = pre.next;
		ListNode next;
		//1-2-3-4-5
		//1-3-2-4-5   --->1-4-3-2-5
		for (int i = 0; i < right - left; i++) {
			next = cur.next;
			cur.next = next.next;
			next.next = pre.next;
			pre.next = next;
		}
		return dummyNode.next;
	}
	public ListNode reverseBetween(ListNode head, int left, int right) {
		ListNode dummy = new ListNode(0);
		dummy.next = head;
		ListNode preNode = dummy;
		//	将preNode移动left-1步，那么他就在第一个需要反转的元素之前
		for (int i = 0; i < left - 1; i++) {
			preNode = preNode.next;
		}
		//	要反转的链表的开始节点就是preNode的下一个节点
		ListNode startNode = preNode.next;
		ListNode nextNode = startNode.next;
		for (int i = 0; i < right-left; i++) {
			startNode.next=nextNode.next;
			nextNode.next=preNode.next;
			preNode.next=nextNode;
			nextNode=startNode.next;
		}
		return dummy.next;
	}
}
